package Tree;

public class _222_CountCompleteTreeNodes {
    int count = 0;
    //time limit exceeded
    public int countNodes_w1(TreeNode root) {
        inorderTraversal(root);
        return count;
    }

    public void inorderTraversal(TreeNode root) {
        if(root==null) return;
        count++;
        inorderTraversal(root.left);
        inorderTraversal(root.right);
    }

    //reference solution:2 steps:1.check if the left tree's high is the same as the right tree.if so,return directly,else
    //divide and conquer
    public int countNodes(TreeNode root) {
        int ldepth = leftDepth(root);
        int rdepth = rightDepth(root);
        if (ldepth == rdepth) {
            return (1 << ldepth) - 1;
        } else {
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
    }

    public int leftDepth(TreeNode root) {
        int depth = 0;
        while (root != null) {
            depth++;
            root = root.left;
        }
        return depth;
    }

    public int rightDepth(TreeNode root) {
        int depth = 0;
        while (root != null) {
            depth++;
            root = root.right;
        }
        return depth;
    }


}
